
// 879.盈利计划
class Solution {
    typedef unsigned long long LL;
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int MOD = 1000000007;
        // 此题是一个二维费用的背包问题
        int sz = group.size(), ret = 0;
        int pro_max = accumulate(profit.begin() , profit.end() , 0);
        if(pro_max < minProfit) return 0;
        vector<vector<LL>> dp(pro_max + 1 ,vector<LL>(n + 1));   
        for(int i = 0 ; i <= n ; i++) dp[0][i] = 1;
        for(int i = 1; i <= sz ; i++)
        {
            int p = profit[i - 1] , g = group[i - 1]; 
            for(int j = pro_max ; j >= 0 ; j--)
            {
                for(int k = n ; k >= g  ; k--)
                {
                    dp[j][k] += dp[max(j - p,0)][k - g];
                    dp[j][k] %= MOD;
                }
            }
        }
        return dp[minProfit][n];
    }
};